package demo10;

/**
 * 二叉树的深搜_二叉搜索树中第k小的元素
 * https://leetcode.cn/problems/kth-smallest-element-in-a-bst/
 */
class Solution1 {
    int ret = Integer.MIN_VALUE;
    int count = 0;
    public int kthSmallest(TreeNode root, int k) {
        this.count = k;
        dfs(root);
        return ret;
    }

    private int dfs(TreeNode root) {
        if(root.left == null && root.right == null) {
            if(count == 0) return root.val;
            count--;
            return ret;
        }
        if(root.left != null) ret = dfs(root.left);
        count--;
        if(count == 0) return root.val;
        if(root.right != null) ret = dfs(root.right);
        return ret;
    }
}